package com.desheng.bigdata.ds.sort;

import com.desheng.bigdata.util.DSUtil;

/**
 * @Description 希尔排序
 * @Author deshenglijun
 * @Date 2020/5/4 21:53
 * @Version 1.0
 */
public class ShellSort {

    /**
     * 使用希尔排序对元素进行交换
     * @param arr
     * @param <T>
     */
    public static <T extends Comparable<T>> void shellSort(T[] arr) {
        int h = 1;
        while(h < arr.length / 2) {
            h = 2 * h + 1;
        }

        while (h > 0) {
            //排序
            for(int i = h; i < arr.length; i++) {
                for (int j = i; j >= h; j -= h) {
                    if(DSUtil.greater(arr, j, j - h)) {
                        DSUtil.swap(arr, j, j - h);
                    } else {
                        break;
                    }
                }
            }
            //进行h的替换
            h = h / 2;
        }
    }
}
